Một số bài toán được biết là NL-đầy đủ theo phép quy về sử dụng bộ nhớ lôgarit, bao gồm liên thông có hướng ST và 2-SAT. Bài toán liên thông có hướng ST hỏi xem có hay không đường đi từ S đến T trong một đồ thị có hướng. Bài toán 2-SAT hỏi xem liệu có hay không một tập giá trị các biến sao cho một biểu thức logic cho trước với mỗi điều kiện là tuyển của hai biến được thỏa mãn. Chẳng hạn như biểu thức sau

( x 1 ∨ x 3 ¯ ) ∧ ( x 2 ¯ ∨ x 3 ) ∧ ( x 1 ¯ ∨ x 2 ¯ ) {\displaystyle (x_{1}\vee {\bar {x_{3}}})\wedge ({\bar {x_{2}}}\vee x_{3})\wedge ({\bar {x_{1}}}\vee {\bar {x_{2}}})}